package Sequence;

public class Test0685 {
    public static void main(String[] args) {
        new Solution0685_1().findRedundantDirectedConnection(new int[][]{{2,1},{3,1},{4,2},{1,4}});
    }
}

class Solution0685_1 {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int length = edges.length;
        int[] records = new int[length+1];
        for (int[] edge : edges) ++records[edge[1]];

        for (int i = length-1; i >= 0; i--) {
            if (records[edges[i][1]] == 2&&!checkCircular(edges,i)) return edges[i];
        }

        for (int i = length-1; i >= 0; i--) {
            if (records[edges[i][1]] == 1&&!checkCircular(edges,i)) return edges[i];
        }

        return null;
    }

    public boolean checkCircular(int[][] edges,int removeIndex) {
        int length = edges.length;
        UnionFind unionFind = new UnionFind(length + 1);

        for (int i=0;i<length;i++){
            if (i==removeIndex) continue;

            if (!unionFind.union(edges[i][0], edges[i][1])) {
                // 合并失败，表示 edges[i][0] 和 edges[i][1] 在一个连通分量里，即构成了环
                return true;
            }

        }

        return false;
    }

    private static class UnionFind {
        // 代表元法
        private final int[] parent;

        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            while (x != parent[x]) {
                // 路径压缩（隔代压缩）
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        public boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);

            if (rootX == rootY) {
                return false;
            }
            parent[rootX] = rootY;
            return true;
        }
    }
}
